5.	Automatic Generation of Object Finding Strategies

5.1	Introduction

	In this section we describe a system which can be rapidly
programmed to find major surfaces in relatively complex 
real-world environments.  Objects are designated to the system
by circling examples with a cursor in a displayed image.
The system then formulates a strategy for finding the object based on
knowledge of available picture processing techniques and about the makeup
of the current pictorial domain.  The resulting program 
is then run on representative scenes and
debugged interactively as errors materialize.  
This work is part of a system which can be rapidly programmed
to find objects in office scenes as described in [1].

	Previously we have used ISIS to develop 
interactively a set of procedures for finding objects in 
office scenes. The basic idea underlying these
strategies   is   to   rapidly   disqualify   obviously
irrelevant  areas  of  the  scene   by   sampling   for
characteristic   attributes   of the desired  object *.
Additional  local  properties  are   then   tested   to
eliminate  those  samples  belonging  to  other objects
which share the acquisition attributes.     The surface
containing the acquired samples is then bounded and the
resulting  region   tested  for  appropriate  size  and
shape. Programs of this sort have been developed for
finding various objects commonly founnd in office  scenes
(including door, table, chair, wall, picture, and floor).

--------------------------------------------------------

* The object being sought will often be referred to as
the  "target object", "target", or, sometimes, just the
object.

--------------------------------------------------------

	A plan  for  finding  a  door  might  consist  of
acquiring  samples  at  a  height likely to contain few
things  besides  a  door,  and   then   validating   by
eliminating   those  samples  which  on  the  basis  of
remaining local attributes have low likelihood of being
part  of  a door. The door boundary is then obtained by
growing a  region  around  the  initial  samples  using
attributes  such as hue and saturation. One alternative
approach would be to first scan downward from  the  top
of  the image to a point whose height is unique to door
and wall. The edge of the  door  is  then  obtained  by
scanning  horizontally  from  this  point,  seeking  an
abrupt change in saturation. (Doors in SRI offices  are
deep  brown  while  walls  are  tan.)  If this edge has
sufficient vertical extent, the door boundary  is  then
inferred from the  known  shape  and  size  of  our
office doors and the local surface orientation measured
in the image on the door's side of  the  discontinuity.
Finally,  the  computed  edges are confirmed by testing
for evidence of the predicted boundaries in the image.

	The above strategies  can be schematized
into  acquisition,  validation,  and  bounding  phases.
Specific  techniques  for  accomplishing each phase are
chosen from available methods on the basis  of  current
information about the pictorial domain.

5.1.1	Acquisition Methods

	The most straightforward way of  acquiring  samples  of
the   object  is  to  filter  random  picture  samples,
rejecting any sample which fails to  pass  a  predicate
descriptive  of  the  desired object.  For example, the
sampled scene may be  filtered  to  retain  only  those
samples  at  a certain height. alternatively, the scene
can be sampled along a locus to  detect  distinguishing
boundary  discontinuities.     These  predicates are
generated automatically from pictorial examples.

5.1.2	Validation Methods

	Acquired  samples  are validated by checking additional
local  characteristics  that  distinguish  the  desired
object  from others with common acquisition attributes.
These   additional   attributes are  examined
sequentially,  reducing the number of samples that must
be examined by successive tests.
Total cost is minimized by deferring
computationally expensive procedures.  When
the  cost of planning the optimal order exceeds  the
known cost of  using  all  remaining  attributes, samples  
are classified  with respect to possible objects.  Those
samples judged likely  to belong to the  desired  object  
are  retained.  Samples along a boundary are further validated 
by testing the boundary length, strength and orientation 
using suitable masks.

5.1.3	Bounding Methods

	The  final  bounding  phase  is accomplished in various
ways.  Given a suitable geometric model of  the  object
and  a  projective  camera  transform,  a procedure can
compute   analytically   the   best   global   boundary
consistent  with  detected  edge points.   The computed
boundary can be projected onto the image and  validated
using extent masks as above.
Procedural models  are  available  for  common  surface
types  such   as   horizontal   and  vertical
rectangles.  In the absence of such  models,  a  region
may  be  grown  around  validated  points; neighbors of
validated samples which pass a chosen predicate  (often
the  acquisition  predicate)  are  added to a push-down
stack. Neighbors of  points  on  this  stack  are  then
examined  recursively.       All  accepted  points  are
collected together into  a  region,  for which a crude  
boundary can  be obtained by computing a convex hull.

5.2	Automatic Generation of Predicates

	The work described here is an attempt to automate three key 
decisions involved in planning a distinguishing features strategy:

	(1) What attributes should be used for acquiring 
	    initial samples?
	(2) What attributes should be used for validating
	    those samples?
	(3) What attributes should be used in region
	    growing to obtain a complete outline?

All three decisions involve distinguishing a desired surface 
in a context of other surfaces that may be present.
Acquisition, for instance, involves distinguishing a surface
from other known surfaces in a domain, validation from
other surfaces known to satisfy the acquisition attributes, and
bounding from all surfaces that could possibly be adjacent
to it in the image.

	In order to explain predicate generation, 
a digression to describe the data base is required.
Objects are characterized by local surface attributes,
symbolic properties, and relations with other objects.
The local surface attributes which are currently used as
descriptors are: brightness, color (separated into hue and 
saturation components),
and, when range data is available, height and local surface orientation
(referred to as "orientation").  Local properties are stored as cumulative 
histograms representing the probability density functions for the
object's attribute values. These histograms allow the probability of
of an object having an attribute in a given range to be computed by a
simple subtraction.  These histograms may be augmented by 
symbolic properties such as
boundary descriptions, size and extent values, surface characteristics
(e.g. horizontal), and spatial relations (e.g. adjacent-to, above,
or left-of). The creation and modification of these descriptions
will be elaborated below.

	A  detector (or a "simple detector") is a procedure 
that checks whether a  sample's  attribute  value  lies
within  a  given  contiguous range of attribute values.
A  "composite detector" is a conjunction of
simple detectors. A  "predicate"  is  the  corresponding LISP
program for a detector.  A predicate returns T (true) if the value 
is within the range, NIL (false) otherwise.  The  terms  detector
and   predicate   will   often  be  used  synonomously.




5.2.1	Design of Acquisition Predicates

	Filtering randomly selected samples
with a predicate which  accepts only those of interest, 
has proved to be an  extremely  useful  acquisition tool in
manual strategies. Acquisition predicates should pass  a  few
points  on  the  desired  object  while  excluding  all
others.  They  should  be  as  cheap  and  reliable   as
possible.  Naturally, these desires are somewhat 
contradictory; usually a detector  that
allows  most  points on the target object to pass, will
also pass some points  from  other  objects.
To overcome this difficulty, the program attempts
to generate compound detectors that exclude all samples from 
undesired objects,  allowing at least a few points
on the desired object to pass. The program  returns a list of any
undesired objects which cannot be completely excluded so that
these may be distinguished subsequent to filtering, using more
expensive global attributes.

	The expected cost and confidence of applying a detector 
can be computed for each object. The  confidence  of  an 
object given a detector is loosely defined as the probability  
that  a sample  accepted  by the detector belongs to the object
in question.     The complete derivation is contained  in
Appendix  1.     Cost is defined as the expected cost
(measured in milliseconds of CPU time) of application 
of the detector to the image. Given a detector and the expected
number  of  points  from  the  set  to be filtered that will be both
part of the object, and accepted
by  the  detector, it is possible to compute the sampling 
frequency and the anticipated  cost. This derivation is also 
contained in Appendix 1.

	The quality of a detector is evaluated using a 
heuristic function of cost and confidence that
reflects the design priorities listed above.
With this detector quality function, Q (described below), the
generation of good compound detectors becomes (for combinatorial reasons) 
a problem in heuristic search.  The search proceeds as follows.
First a good initial set of simple detectors is selected. 
The candidate detector with the best Q is then combined with others to see
if the combination improves the Q function. The best combination, 
in turn, is combined with remaining candidates and so on,
until a terminating
condition is reached; either the set of candidates is exhausted,
some combination exceeds a preset Q threshold, or some effort
bound is exceeded.

	The heuristic quality function, Q, which is used to
order a set of detectors, is shown graphically
in Figure 29.  Its maximum value is the  confidence
of  the  object and detector (which cannot be
greater than 1.0) and it's minimum value is 0. The cost of
applying  the  detector  determines  where the detector
falls on the curve.  For equal  confidence,  and  costs
below  a  certain minimum, MINCST (currently equal to 2
seconds), the Q function is  indifferent  as  to  which
detector  is  selected.   For  costs  above  a  certain
maximum, MAXCST (now set to 100 seconds), the  function
returns  0.  In essence, any cost below MINCST is effectively
zero and any cost above MAXCST  is effectively
infinite.  In between, the curve is linear with a slope
determined by the confidence, MINCST and MAXCST.     By
making  the maximum value of Q be the confidence, added
emphasis  is  given  to  the  goal  of  producing  high
confidence  tests.     Of  two competing tests, the one
with lower confidence must also  have  lower  costs  in
order   to   be   considered   better.  Q  was  defined
empirically to provide the  functional  characteristics
detailed  above.  The parameter values were also chosen
empirically on the basis of best results.

	Two heuristics are used to select candidate 
simple detectors. The  first uses the
function, PEAKS, to locate peak  attribute  values  for
the  object. PEAKS examines the characterization of the
object (which are probability density curves  and  will
be  discussed  later)  for  a  peak providing a certain
minimum area underneath.  The function will then narrow
the   peak  if  it  can  do  so  without  significantly
decreasing the area. Minimum acceptable peak  size  and
other  variables are empirically determined parameters.
PEAKS which currently can only find a single  peak  for
each attribute curve, outputs a set of simple detectors
corresponding to the attributes considered.

	The   second   selection   program,   MINRANGE,
generates   distinguishing  detectors  by  looking  for
contiguous ranges of attribute  values  which  minimize
the  set of ambiguous objects.  This is accomplished by
scanning a range of an attribute for the target object,
checking  to  see  what  other objects share the range.
MINRANGE also returns a set of single detectors.

	The  present  implementation  of  the heuristic
predicate generator creates only composite detectors from the
initial set supplied by PEAKS and MINRANGE.
The program cannot yet generate detectors which are disjunctions 
(such as might be required  for  locating  a  red  and  white
checkered   tablecloth), or decision trees.  Despite these
limitations (which will probably be removed in the future),
the detectors  generated  are quite effective.

	To generate these composite detectors, the program,  DACQ
(Default  ACQuisition),  selects  the  current best (in
terms of Q) detector on the list and tries  to  combine
it  with  all the simple detectors on the initial list.
Detectors which would  violate  the  description  given
above (e.g., which would combine two detectors with the
same attribute), or those where the  composite  doesn't
have  a  smaller ambiguity set than the parents are not
considered.  When a candidate is selected, a  composite
detector is formed and retained only if its value of
Q is higher than that of both parents.   Before  adding
the  new  candidate to the appropriate spot in the list
of detectors, a quick check is made to see if it  could
ever  be better than the current best detector. This is
done by computing Q for a  hypothetical  detector  with
the  same  cost, but with a confidence of 1.   If the Q
of this combination is higher than the best Q  so  far,
the new candidate is kept.  Otherwise, it is discarded.

	A  candidate  that is retained, is added to the
proper location in  the  ordered  list  of  candidates.
After  the  first  detector has been tried with all the
possible single detectors, it is marked as having  been
expanded,  and DACQ iterates with the new list.   If no
candidates were retained, DACQ continues with the  next
best detector on the list.

	When  there  are  no more candidates, or when a
detector  is  generated  with  a  Q  above  a   certain
threshold,   the  program  terminates,  returning  the
complete ordered list of detectors generated.

	DACQ spends considerable time  attempting
minor  improvements to its best candidates.  Therefore,
a CPU time limit was provided  to  allow  the  user  to
decide  how  much  effort DACQ should expend.    If the
time quantum provided by  the  user  is  exceeded,  the
program interrupts, prints the best candidate, and asks
the user whether it should continue.  If the  reply  is
NO, or there is no reply within ten seconds (equivalent
to a NO reply), DACQ terminates with the best  so  far.
If  the  user wishes to proceed, DACQ will continue for
another quantum of time.  The  predicates  produced  by
DACQ  within  the  time constraints (currently about 10
seconds) are typically the same as  those  produced  by
letting  it  run  to  completion.  Also,  the detectors
produced are usually as good or better than  predicates
defined  manually  by  experienced users and often they
are the same!

	The  final  steps  in  the  automation  of  
filtering are straightforward.  The best compound detector
is converted to an  equivalent  LISP LAMBDA expression 
which is then compiled and saved. The system already knows
what sampling density  is  required  for  the  detector,
since  it  is a by-product of the cost computation (see
Appendix 1).  The image is then randomly sampled at the 
appropriate density, and the resulting samples are filtered 
with the LISP predicate to obtain a few acquisition samples.
These samples may need further validation tests to discriminate
residual ambiguities. Examples are found in section 5.3.



5.2.2	Design of Bounding Predicates

	The next step in object finding after validating the acquisition
samples is to extract the boundary of the surrounding surface
Bounding a single specific object is a significanntly different
task than the global scene partitioning described in Section IV 
of this report.

	In object bounding, a region is grown from 
acquisition samples by including all contiguous samples 
which satisfy an appropriate bounding predicate. Specifically, 
the program, GROW, applys the predicate  to samples 
adjacent to the acquisition samples.  If a sample is 
accepted, its neighbors (either 4-adjacent or 8-adjacent) 
are added to  a  list  to  be recursively  examined.  
When all possible samples have accreted to the original 
set, GROW returns the resulting new region.

	The bounding predicates differ from acquisition 
predicates in two important ways. First, the particular region 
being bounded need only be distinguished from pictorially adjacent 
objects, as opposed to all objects in the scene. Second, 
region growth requires predicates capable of collecting all points 
on the object. 

	The basic region grower can be speeded up by scanning
out horizontally and vertically from the initial acquisition
samples until a discontinuity is detected. Points located  
on  the  boundary are  then joined into a new, larger region, 
and GROW used to fill in any holes.
Scanners are good for quickly locating
edges, but suffer by requiring that all points  between
the  starting point and the desired edge point pass the
predicate.  A point that fails,  terminates  the  scan.
The  region  grower  is less directed, but as a result,
can "go around" isolated  points  where  the  predicate
fails.  The combination of scanning and growing has proven
very effective.

	Since the predicate must accept all  points  on
the object, the task of generating an initial predicate
is greatly simplified--we need  only  create  detectors
based  on  the  complete  range  for  all attributes (a
"full-range detector"). There is relatively little risk in 
using these wide range detectors, since they need only 
discriminate objects adjacent to the acquired object.
However, if the system has specific
knowlege about object adjacencies, the full-range predicate
can be refined by conjoining it with negated full-range
predicates for those adjacent objects.

	A major shortcoming of the above approach
is  that  the  region growing predicates are
applied uniformly to all points.  Often,
it  is  known that the color (say) of a region is
darker at the bottom than at the top. Such  information
should  be  used to produce more selective predicates
that respond differently at different points in the  region.   
Predicates could also be designed which continuously change 
their expectation of what should come next, based on what 
has  recently been seen.

	Other shortcomings are due  to  poor  predicate
specification from the outset.  This can arise from the
system  receiving  an  incomplete  description  of  the
object  initially,  perhaps  not  knowing  enough about
other objects in the environment, or often not  knowing
of  good descriptors which although obvious to a person
may  not  be  obvious  to  the  system. Remedies for these
shortcomings will be discussed in an upcoming dissertation [25].

	In the coming months, the semantic segmentation 
techniques described in Section IV will be studied 
as an alternative means of bounding objects.  
GROW functions strictly by growing regions outward from initial
kernal points on the target object.  The other segmentation
system could be used to grow simultaneously from kernals on the
target and on adjacent objects.  Additional knowledge about 
relationships of the target and its neighbors could be utilized
to obtain improved boundaries.




5.3	Examples


	Figures 30 through 37 illustrate the object 
finding process using the image shown in Figure 1b. 
The objects to be located 
are the picture and the major surfaces of the chair, the 
seat and the back. These objects (along with others
which appear in the image) were shown to the system in other
images of the same scene.  Descriptions were automatically 
generated and from these 
the system was able to create strategies for locating
the objects. In the figures, the regions created in the
course of locating the objects are generally shown as a
boundary with a few points inside. The boundaries (in this
case) are convex hulls created from the samples by ISIS in
order to emphasize the region for the user. 
In the LISP predicates mentioned below, the function LIMITP
is used as the primary detector function. its format is:
(LIMITP attribute sample low high).  LIMITP returns T if
the attribute of the sample lies within the range from
low to high.

	The first example shows the system 
locating the picture. Figure 30 gives the result of
filtering a random sampling of the image with the predicate 	
(LAMBDA (X) (LIMITP (FUNCTION HEIGHT) X 3.19 4.76)).
This predicate keeps only samples at a height
within the range of 3.19 feet to 4.76 feet. Since only
points from the wall, door, and picture should be found at
this height, the validation phase need only distinguish
among these three objects. The results of validation are
shown in Figure 31. The system then grows the region shown
in Figure 32 with the predicate 
(LAMBDA (X) (AND (PICP X) (NOT (WALLP X)))).
PICP * is a LISP predicate function, generated by the system
which returns T if the sample has the properties of the picture.
WALLP is a similar predicate for the wall. the complete growth predicate
requires that the sample look like a picture point, but not
like a wall point.

--------------------------------------------------------

* These predicates are conjunctions of full range predicates for
the objects in question. That is, they check that the value of 
each attribute of a sample falls within the possible
range of values for the object in question.

---------------------------------------------------------

	In Figures 33 through 37, the system locates the 
chair seat and back. In Figure
32, the sampled scene has been filtered for points on the
chair back, using the predicate 
(LAMBDA (X) (AND (LIMITP HEIGHT X 1.62 2.14)
                 (LIMITP HUE X  0.0 6.1))).
This predicate checking height and hue,
selects only the single sample shown in the right middle of
the chair back in Figure 33. The sample is retained during
validation, and used as a starting point for the region
grower which generates and uses a predicate to discriminate the
samples of the back from those of adjacent table and wall
areas resulting in the region shown in figure 34.

	The acquisition, validation, and bounding process 
for the chair seat is shown in Figures 35 through 37.
The region shown in Figure 35 is the result of
filtering with the predicate 
(LAMBDA (X) (AND (LIMITP HEIGHT X 1.09 1.62)
                 (LIMITP ORIENT X 0.0 36.0))),
which selects samples with height and orientation 
appropriate for the chair seat. One point is eliminated
during validation, since its color does not match that of the
seat, giving the region shown in Figure 36. Finally,
Figure 37 shows the results of growing with a predicate which
distinguishes the seat from the floor and the wall.